import java.util.*;

public class MemoizingDynamic extends PathAlg {
	
	// This _could_ be a list of hashmaps, but the list would then need to have
	// size equal to the sum of the weights along the longest Hamiltonian path,
	// minus the last edge. This way is also easier to program.
	private HashMap<String, List<AlgRet>> M
				= new HashMap<String, List<AlgRet>>();
	
	public String getName()
	{
	    return "Memoizing Dynamic Programming";
    }
    
	public void runAlgorithm()
	{
		int[] nodes = new int[costs.length];
		for(int i=0; i<costs.length; ++i) {
			nodes[i] = i;
		}
		nodes[0] = -1; // First node already visited
		AlgRet ret = opt(0, nodes);

		this.expectedLatency = ret.el;
		this.path = ret.path;
	}
	
	private AlgRet opt(int node, int[] nodes)
	{
		AlgRet ret = null;
		final String hash = hash(nodes);
		List<AlgRet> candidates = M.get(hash);
		float retEL = 0;
		
		// If the remaining nodes already have been calculated
		if(candidates != null) {
			for(AlgRet tmp : candidates) {
				final float tmpEL = tmp.el + costs[node][tmp.getFst()]*tmp.pp;
    			if(ret == null || tmpEL < retEL) {
    				ret = tmp;
					retEL = tmpEL;
    			}
			}

			ret = new AlgRet(ret);
		}
		else {
			candidates = new LinkedList<AlgRet>();
    		for(int i : nodes) {
    			// If node has already been visited
    			if(i == -1) {
    				continue;
    			}
    			
    			nodes[i] = -1; // Mark node as visited
				
    			AlgRet tmp = opt(i, nodes);
    			
    			// If we've found a minimum
				final float tmpEL = tmp.el + costs[node][tmp.getFst()]*tmp.pp;
    			if(ret == null || tmpEL < retEL ) {
    				ret = tmp;
					retEL = tmpEL;
    			}
    			
    			nodes[i] = i; // Leave node
				candidates.add(new AlgRet(tmp));
    		}
    		
    		// If all nodes were visited, we're at a leaf
    		if(ret == null) {
    			return new AlgRet(node);
    		}
    		
    		// Memorize candidates
    		M.put(hash, candidates);
    	}
		
		// Add the current node to the return object
		ret.addNode(node);
		
		return ret;
	}
	
	private String hash(int[] l)
	{
		String ret = "";
		for(int i : l) {
   			ret += ","+i;
		}
		
		return ret;
	}
	
	private class AlgRet {
		public float el;
		public int[] path;
		public float pp;
		public int fst;
		
		public AlgRet(AlgRet other)
		{
		    this.el  = other.el;
		    this.pp  = other.pp;
		    this.fst = other.fst;
		    
		    this.path = new int[other.path.length];
		    System.arraycopy(other.path, 0, this.path, 0, other.path.length);
		}
		
		public AlgRet(int node)
		{
			this.el = 0;
			this.pp = probabilities[node];
			
			this.path = new int[costs.length];
			for(int i=0; i<this.path.length; ++i) {
				this.path[i] = -1;
			}
				
			this.fst = this.path.length - 1;
			this.path[fst] = node;
		}
		
		public void addNode(int node)
		{
			this.el += costs[node][this.getFst()] * this.pp;
			this.path[--fst] = node;
			this.pp += probabilities[node];
		}
		
		public int getFst()
		{
			return path[fst];
		}
	}
}
